package list.ReverseList;

import list.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName changeList
 * @Description TODO
 * @Author lenovo
 * @Date 2023-02-17 11:24
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class ChangeList {
    /**
     给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

     你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     24. 两两交换链表中的节点
     给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

     示例 1：

     输入：head = [1,2,3,4]
     输出：[2,1,4,3]
     示例 2：

     输入：head = []
     输出：[]
     示例 3：

     输入：head = [1]
     输出：[1]
     */

    public ListNode swapPairs(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();

        ListNode yummy = new ListNode(0);
        yummy.next = head;
        ListNode cur = yummy;

        while (true) {
            int count = 0;
            ListNode temp = head;

            while (temp != null && count < 2){
                stack.push(temp);
                temp = temp.next;
                count++;
            }

            if (count != 2){
                cur.next = head;
                break;
            }

            while (!stack.isEmpty()){
                ListNode popListNode = stack.pop();
                cur.next = popListNode;
                cur = cur.next;
            }
            head = temp;
        }
        return yummy.next;
    }

    public static void main(String[] args) {
        ChangeList changeList = new ChangeList();
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        System.out.println(changeList.swapPairs(head1));
    }

}